Leetcode 327.Count of Range Sum 题解

题目链接

题目内容

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note: A naive algorithm of O(n^2) is trivial. You MUST do better than that.

Example: Input: nums = [-2,5,-1], lower = -2, upper = 2, Output: 3 Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

解题思路

首先，为了避免重复的求和，我想到的是先把我们的输入的数组转化成一个代表前i个数之和的数组Sum,再对该数组进行处理，因为我们求第j位到第i位的和只需要求Sum(j,i) = Sum(j) - Sum(i)即可求到[i, j) 范围的数字之和，即第i个数字到第j-1个数字之和。

为了方便计算，我的Sum数组中，Sum[0]设为0，Sum[i]准确表示到第几个数字之和 = Sum[i] - Sum[0]

有了以上的转变之后，我们的求法就简单了

由于我是为了练习归并算法为目的选择的这个题目，所以我在解决时用到了类似归并的思路。

通过不断把问题拆分成前一半范围中符合要求的个数+后一半范围中符合要求的个数+当前范围中符合要求的个数，并在拆分到只剩下一个数字的时候return,通过这样的归并算法得到最终的结果。

因为在合并时，前一半和后一般的数量已计算出且数组有序，因此，当前范围中计算个数和合并的时间复杂都均是O(N)，所以整体的复杂度为O(N*logN)

题目代码

class Solution {
public:
    int mergeAnlyse(vector<long>& sum, int lower, int upper, int l, int r) {
        if (r - l <= 1)
            return 0;
        int mid = (r + l)/2, m = mid, n = mid, ans = 0;
        ans = mergeAnlyse(sum, lower, upper, l, mid) + mergeAnlyse(sum, lower, upper, mid, r); //问题拆分
        for (int i = l; i < mid; i++) {
            while(m < r && sum[m] - sum[i] < lower)
                m++;
            while(n < r && sum[n] - sum[i] <= upper)
                n++;
            ans += n - m;
        } //通过遍历寻找当前范围中符合要求的个数
        inplace_merge(sum.begin() + l, sum.begin() + mid, sum.begin() + r); //使用STL库中的函数实现归并
        return ans;
    }

    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int len = nums.size();
        vector<long> tmp(len + 1, 0);
        for(int i = 0; i< len; i++)
            tmp[i+1] = tmp[i] + nums[i];
        return mergeAnlyse(tmp, lower, upper, 0, len+1);
    }
};

总结

个人觉得这个题目的关键点其实就在于把原先数组转变成一个和的数组方便计算第i个数字到第j-1个数字之和这个做题技巧，而归并算法方面的难度并不大，只要懂得在我们的归并算法中结合归并排序，我们就可以在每一次寻找符合范围个数的时候都可以通过O(N)的复杂度就得到结果，从而使算法的复杂度降低到O(N*LogN)